#include "rbstrom.h"
#include "pamet.h"

template<class T>
T RBstrom<T>::pridej(T q){
  if(!t){
    t=new RBuzel<T>(q);
    malopameti(t);
    t->zmenC();
    return q;
  }else{
    RBuzel<T> *u=t,*v,*w,*o;
    long nenalezl;
    while(1){
      nenalezl=cmp(q,u->U());// rika, zda je p>u (>0), nebo zda p==u (0), pripadne zda p<u (<0)
      if(nenalezl){
        v=nenalezl>0?u->P():u->L();
        if(v) u=v; else break;
      }else return u->U();
    }
    if(nenalezl>0){
      u->P(new RBuzel<T>(q));
      malopameti(u=u->P());
    }else{
      u->L(new RBuzel<T>(q));
      malopameti(u=u->L());
    }
    while(u->O()){
      v=u->O();
      if(v->C()){
        if(v->O()){
          o=v->O();
          w=v->lS()?o->P():o->L();
          if(w&&w->C()){
            v->zmenC();
            w->zmenC();
            o->zmenC();
            u=o;
          }else{
            if(u->lS()==v->lS()){
              o->O()?(o->lS()?o->O()->L(v):o->O()->P(v)):(t=v,v->O(NULL));
              u->lS()?(o->L(v->P()),v->P(o)):(o->P(v->L()),v->L(o));
              v->zmenC();
              o->zmenC();
            }else{
              o->O()?(o->lS()?o->O()->L(u):o->O()->P(u)):(t=u,u->O(NULL));
              v->lS()?(o->L(u->P()),u->P(o),v->P(u->L()),u->L(v))
	             :(o->P(u->L()),u->L(o),v->L(u->P()),u->P(v));
              u->zmenC();
              o->zmenC();
            }
            break;
          }
        }else{
          v->zmenC();
          break;
        }
      }else break;
    }
    return q;
  }
}

template<class T>
int RBstrom<T>::uber(T q){
  if(!t) return 0;
  RBuzel<T> *u=t,*v,*o,*w;
  long nenalezl;
  char l;
  do{
    nenalezl=cmp(q,u->U());
    if(nenalezl) u=nenalezl>0?u->P():u->L();
  }while(u&&nenalezl);
  if(nenalezl) return 0;
  if(u->L()&&u->P()){
    v=u->L();
    while(v->P()) v=v->P();
    u->U(v->U());
    u=v;
  }
  if(u->O()){
    o=u->O();
    l=u->lS();
    if(u->C()){
      l?o->L(NULL):o->P(NULL);
      delete u;
    }else if(u->L()||u->P()){
      l?(u->L()?(o->L(u->L()),u->L(NULL)):(o->L(u->P()),u->P(NULL)),o->L()->zmenC())
       :(u->L()?(o->P(u->L()),u->L(NULL)):(o->P(u->P()),u->P(NULL)),o->P()->zmenC());
      delete u;
    }else if(o->C()){
      l?o->L(NULL):o->P(NULL);
      delete u;
      v=l?o->P():o->L();
      u=l?v->L():v->P();
      if(u){
        o->O()?(o->lS()?o->O()->L(u):o->O()->P(u)):(t=u,u->O(NULL));
        l?(o->P(NULL),u->L(o),v->L(NULL),u->P(v)):(o->L(NULL),u->P(o),v->P(NULL),u->L(v));
        o->zmenC();
      }else{
        o->O()?(o->lS()?o->O()->L(v):o->O()->P(v)):(t=v,v->O(NULL));
        l?(o->P(NULL),v->L(o)):(o->L(NULL),v->P(o));
        o->zmenC();
        v->zmenC();
        u=l?v->P():v->L();
        if(u) u->zmenC();
      }
    }else{
      l?o->L(NULL):o->P(NULL);
      delete u;
      while(o){
        l?(u=o->P(),v=u->L(),w=u->P()):(u=o->L(),v=u->P(),w=u->L());
        if(u->C()){
          o->O()?(o->lS()?o->O()->L(u):o->O()->P(u)):(t=u,u->O(NULL));
          l?(o->P(v),u->L(o)):(o->L(v),u->P(o));
          o->zmenC();
          u->zmenC();
        }else{
          if(!(v&&v->C())&&!(w&&w->C())){
            u->zmenC();
            if(o->C()){
              o->zmenC();
              break;
            }else{
              l=o->lS();
              o=o->O();
            }
          }else{
            if(v&&v->C()){
              o->O()?(o->lS()?o->O()->L(v):o->O()->P(v)):(t=v,v->O(NULL));
              l?(o->P(v->L()),v->L(o),u->L(v->P()),v->P(u))
	       :(o->L(v->P()),v->P(o),u->P(v->L()),v->L(u));
              o->C()?o->zmenC():v->zmenC();
              break;
            }else{
              o->O()?(o->lS()?o->O()->L(u):o->O()->P(u)):(t=u,u->O(NULL));
              l?(o->P(v),u->L(o)):(o->L(v),u->P(o));
              if(o->C()) {o->zmenC();u->zmenC();}
              w->zmenC();
              break;
            }
          }
        }
      }
    }
  }else{
    t=u->L()?u->L():u->P();
    u->L(NULL);u->P(NULL);delete u;
  }
  return 1;
}
